package com.company.ljh.hard;

import java.util.Stack;

/**
 * @description:
 * 42. 接雨水
 *          1
 * 1        1
 * 1    1   1
 * 1 1  1 1 1
 * 1 1  1 1 1
 * @projectName:leet_code
 * @see:com.company.ljh.hard
 * @author:ljh
 * @createTime:2024/4/2 10:26
 * @version:1.0
 */
public class 接雨水 {
    public static void main(String[] args) {
        int[] height = new int[]{4,2,0,3,2,5};
        int trap = trap(height);
        System.out.println(trap);
    }

    /**
     * 解法1:通过栈的方式，每次入栈和前面的进行比较，按层进行计算，通过与当前已计算的高度和上一个的距离计算面积
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        Stack<Integer[]> stack = new Stack();
        int total = 0;
        for (int i = 0; i < height.length; i++) {
            //记录已经计算面积的高度
            int tempHeight = 0;
            while (!stack.isEmpty() && height[i] != 0 && tempHeight < height[i]) {
                Integer num[] = stack.peek();
                //当栈中的高度小于当前入栈的高度，将栈中的出队（单调栈）
                if(stack.peek()[0] <= height[i]){
                    stack.pop();
                }
                int distince = (i - num[1] -1);
                //计算有效高度，如果栈中高度超过了当前高度，以当前高度为准
                int thisHeight = num[0] < height[i] ? num[0]:height[i];

                total += distince* (thisHeight - tempHeight);

                tempHeight = thisHeight;
            }

            if (height[i] != 0)
                stack.push(new Integer[]{height[i], i});
        }
        return total;
    }
}
